#include<iostream>
#include<vector>
#include<queue>
#include<set>

using namespace std;

class Solution {
public:
	vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
		queue<pair<int, int>> q;
		set<pair<int,int>> set;
		int origin = image[sr][sc];
		q.push(make_pair(sr, sc));
		set.insert(make_pair(sr, sc));		
		while (!q.empty()) {
			int cur_sr = q.front().first;
			int cur_sc = q.front().second;
			image[cur_sr][cur_sc] = color;
			if (cur_sr - 1 >= 0 && image[cur_sr - 1][cur_sc] == origin) {
				if (set.count(make_pair(cur_sr-1,cur_sc))!=1) {
					q.push(make_pair(cur_sr - 1, cur_sc));
					set.insert(make_pair(cur_sr - 1, cur_sc));
				}
			}
			if (cur_sr + 1 < image.size() && image[cur_sr + 1][cur_sc] == origin) {
				if (set.count(make_pair(cur_sr+1,cur_sc)) != 1) {
					q.push(make_pair(cur_sr + 1, cur_sc));
					set.insert(make_pair(cur_sr + 1, cur_sc));
				}
			}
			if (cur_sc - 1 >= 0 && image[cur_sr][cur_sc - 1] == origin) {
				if (set.count(make_pair(cur_sr, cur_sc - 1)) != 1) {
					q.push(make_pair(cur_sr, cur_sc - 1));
					set.insert(make_pair(cur_sr, cur_sc - 1));
				}
			}
			if (cur_sc + 1 < image[0].size() && image[cur_sr][cur_sc + 1] == origin) {
				if (set.count(make_pair(cur_sr, cur_sc + 1))!=1) {
					q.push(make_pair(cur_sr, cur_sc + 1));
					set.insert(make_pair(cur_sr, cur_sc + 1));
				}
			}
			q.pop();
		}
		return image;
	}
};

void main() {
	vector<vector<int>> image = {
		{1,1,1},
		{1,1,0},
		{1,0,1}
	};
	Solution s;
	s.floodFill(image,1,1,2);
}